/*
 * @lc app=leetcode.cn id=191 lang=csharp
 *
 * [191] 位1的个数
 */

// @lc code=start
public class Solution {
    public int HammingWeight(int i) {
        i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
        i = (i * (0x01010101) >> 24);
        return i;
    }
    
    /*
    i    1010 1100
    0x55 0101 0101
    0x33 0011 0011
    0x0f 0000 1111
    
      
    i       1010 1100
    0x55    0101 0101
    i&0x55  0000 0100 -- 每两位中低位1的个数
    
    i>>1        0101 0110
    0x55        0101 0101
    i>>1&0x55   0101 0100 -- 每两位中高位1的个数
    
    i&0x55 + i>>1&0x55
    0000 0100 + 0101 0100 = 0101 1000 -- 每两位中1的个数
    
    
    i       0101 1000
    0x33    0011 0011
    i&0x33  0001 0000 -- 每四位中较低低2位中1的个数
    
    i>>2        0001 0110
    0x33        0011 0011
    i>>2&0x33   0001 0010 -- 每四位中较高2位中1的个数
    
    i&0x33 + i>>2&0x33
    0001 0000 + 0001 0010 = 0010 0010 -- 每四位中1的个数
    
    
    i      0010 0010
    0x0f   0000 1111
    i&0x0f 0000 0010 -- 每八位中较低4位中1的个数
    
    i>>4       0000 0010
    0x0f       0000 1111
    i>>4&0x0f  0000 0010 -- 每八位中较高4位中1的个数
    
    i&0x0f + i>>4&0x0f
    0000 0010 + 0000 0010 = 0000 0100 -- 每八位中1的个数 (4)
    
    
i = (i * (0x01010101) >> 24);
是将32位整数中每8位的1的个数相加，得到整个32位整数中1的总个数。
在这一步中，我们首先将整数 `i` 与 `0x01010101` 相乘。这个操作的效果是将 `i` 中每8位的1的个数相加，然后将结果放在最高的8位中。这是因为 `0x01010101` 是一个特殊的常数，它的二进制表示是 `00000001 00000001 00000001 00000001`。当它与 `i` 相乘时，`i` 中每8位的1的个数会被加到最高的8位中。


为啥结果放在了最高的8位中，参考10进制乘法,错位相加
                        0000 0100  0000 0100  0000 0100  0000 0100  
                x       0000 0001  0000 0001  0000 0001  0000 0001
                ---------------------------------------------------
                        |0000 0100|  0000 0100  0000 0100  0000 0100
             0000 0100  |0000 0100|  0000 0100  0000 0100 --中间的0省略了， 超过32位的也要省略
  0000 0100  0000 0100  |0000 0100|  0000 0100
    。。。。。。。。        最高8位
                ---------------------------------------------------
    */
}
// @lc code=end

